package Demo3;

import java.util.*;
// 定义二维点类
class MyPoint {
    double x;
    double y;

    public MyPoint(double x, double y) {
        this.x = x;
        this.y = y;
    }
    // 计算该点到另一点的距离
    public double distance(MyPoint p) {
        double dx = x - p.x;
        double dy = y - p.y;
        return Math.sqrt(dx * dx + dy * dy);
    }
}
public class ClosestPair {
    public static void main(String[] args) {
        // 测试数据: n = 4, (x, y) 对: (0, 0), (1, 1), (2, 2), (3, 3)
        //                           (0, 0), (1, 1),(1, 1.5),(3, 3)
        int n = 4;
        MyPoint[] points = new MyPoint[n];
        points[0] = new MyPoint(0, 0);
        points[1] = new MyPoint(1, 1);
        points[2] = new MyPoint(1, 1.5);
        points[3] = new MyPoint(3, 3);

        // 根据 x 坐标对点数组按照从小到大进行排序排序
        Arrays.sort(points, (o1, o2) -> Double.compare(o1.x, o2.x));

        // 计算最近点对的最小距离
        double minDistance = closestPair(points, 0, n - 1);
        System.out.printf("The minimum distance is: %.4f", minDistance);
    }

    // 计算最近点对的距离
    private static double closestPair(MyPoint[] points, int left, int right) {
        // 如果只有一个点或没有点，则返回正无穷
        if (left >= right) {
            return Double.POSITIVE_INFINITY;
        }
        // 如果只有两个点，则直接计算距离并返回
        else if (right - left == 1) {
            return points[left].distance(points[right]);
        }
        // 否则，递归地进行分治计算
        else {
            int mid = (left + right) / 2;
            double leftDistance = closestPair(points, left, mid);//计算出左边子数组中最近点对的距离
            double rightDistance = closestPair(points, mid + 1, right);//计算出右边子数组中最近点对的距离

            //比较左边子数组和右边子数组中最近点对的距离，找到其中较小的距离
            double minDistance = Math.min(leftDistance, rightDistance);

            // 创建一个用于存储中间区域点的列表
            ArrayList<MyPoint> strip = new ArrayList<>();
            for (int i = left; i <= right; i++) {// 将位于中间区域的点加入列表
                if (Math.abs(points[i].x - points[mid].x) < minDistance) {
                    strip.add(points[i]);
                }
            }
            // 根据 y 坐标对中间区域的点列表按照从小到大排序
            Collections.sort(strip, (o1, o2) -> Double.compare(o1.y, o2.y));

            int size = strip.size();
            // 在排序后的中间区域点列表中寻找最近距离的点对
            for (int i = 0; i < size - 1; i++) {
                for (int j = i + 1; j < size && strip.get(j).y - strip.get(i).y < minDistance; j++) {
                    double distance = strip.get(i).distance(strip.get(j));
                    if (distance < minDistance) {
                        minDistance = distance;
                    }
                }
            }
            return minDistance;
        }
    }
}
